package com.example;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Stack;

public class Main {
    //enter 'psvm' to create 'main' method
    public static void main(String[] args) {
//        System.out.println("Hello world!");

//        int a = Integer.valueOf("00001", 2);
//        int b = Integer.valueOf("00010", 2);
//        int c = Integer.valueOf("00100", 2);
//        int d = Integer.valueOf("01000", 2);
//        int e = Integer.valueOf("10000", 2);
//        int val = Integer.valueOf("11111", 2);
//        int p;

//        System.out.println(a + " " + b + " " + c + " " + d + " " + e);

        //&:都1则1  |:有1则1   ^:相同为0，不同为1
//        p = c;
//        System.out.println("p & val \n" +
//                Integer.toBinaryString(p) + "\n" +
//                Integer.toBinaryString(val) + "\n" +
//                (p & val) + "\n");

//        Dp2Px();

        //中缀转后缀
//        initPri();
//        suffix("11.1+2.2-2.1");
//        System.out.println("s1=" + s1.toString());
//        System.out.println("s2=" + s2.toString());
//        calcSuffix();

        //排序
//        int[] array = {9, 8, 7, 6, 5, 4, 3, 2, 1};
//        int[] array = {9, 1, 2, 3, 4, 5, 6, 7, 8};
//        int[] array = {5, 4, 8, 7, 9, 2, 6, 1, 3, 0};
//        int[] array = {30, 20, 41, 31, 4, 42, 17, 32, 10, 43, 23, 33, 18, 44, 14, 34, 28, 45, 8, 11, 35, 46, 9, 21,
//                1, 47, 36, 29, 12, 37, 48, 2, 22, 38, 15, 13, 27, 39, 16, 19, 5, 40, 24, 7, 50, 6, 25, 49, 3, 26};
//        System.out.print("排序前 ");
//        displayArray(array);

        /*int size = 50000;
        ArrayList<Integer> list = new ArrayList<>();
        Random random = new Random();
        for (int i = 0; i < size; i++) {
            list.add(random.nextInt(size) + 1);
        }
        int index = 0;
        Iterator iterator = list.iterator();
        int[] arrsrc = new int[list.size()];
        while (iterator.hasNext()) {
            arrsrc[index] = (int) iterator.next();
            index++;
        }
        while (iterator.hasNext()) {
            arrsrc[index] = (int) iterator.next();
            index++;
        }
        array = arrsrc.clone();
        System.out.println("Size=" + list.size() + " " + Arrays.toString(array));

        long s = System.currentTimeMillis();
        bubbleSort(array);
        long e = System.currentTimeMillis();
        System.out.println("bubbleSort useTime:" + (e - s));

        s = System.currentTimeMillis();
        choiceSort(array);
        e = System.currentTimeMillis();
        System.out.println("choiceSort useTime:" + (e - s));

        s = System.currentTimeMillis();
        insertSort(array);
        e = System.currentTimeMillis();
        System.out.println("insertSort useTime:" + (e - s));*/

//        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
//        int key = 10;
//        System.out.println("find num " + key + " index=" + dichotomyFind(arr, key, 0, arr.length));
    }

    /**
     * ===========================================================================================================================
     */

    //二分查找-递归 , 查找集合必须有序
    public static int dichotomyFind(int[] arr, int key, int min, int max) {
        int mid = arr[max / 2];
        if (key == mid) return mid;
        else if (key > mid) {
            min = mid + 1;
            max = arr.length - 1;
            dichotomyFind(arr, key, min, max);
        } else if (key < mid) {
            min = 0;
            max = mid - 1;
            dichotomyFind(arr, key, min, max);
        }
        return -1;
    }

    /**
     * 简单排序算法
     */
    static int[] testarr2 = {30, 20, 4, 17, 10, 23, 18, 14, 28, 8, 11, 9, 21, 1, 29, 12, 2, 22, 15, 13, 27, 16, 19, 5, 24, 7, 6, 25, 3, 26};
    static int[] testarr = {5, 4, 8, 7, 9, 2, 6, 1, 3, 0};

    public static void displayArray(int[] arr) {
        System.out.print("array=");
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    //冒泡
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            boolean flag = true;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                    flag = false;
                }
            }
            if (flag) break;
//            System.out.print("第" + (i + 1) + "轮  ");
//            displayArray(arr);
        }
    }

    //选择
    public static void choiceSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) minIndex = j;
            }
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
//            System.out.print("第" + (i + 1) + "轮  ");
//            displayArray(arr);
        }
    }

    //直接插入
    public static void insertSort(int[] arr) {
        //将数组中下标为0的元素当成是有序序列中的元素，所以i从1开始，取无序序列中的第一个元素，选择合适位置插入
        int j;
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];//要插入的元素
            j = i;
            while (j > 0 && arr[j - 1] > tmp) {//要插入的数据的前一个肯定是有序的，如果前一个数据比要插入的数据大，那么将前一个后移
                arr[j] = arr[j - 1];
                j--;//再次向前比较
            }
            //前一个小于或等于要插入的数据
            arr[j] = tmp;
//            System.out.print("第" + (i + 1) + "轮  ");
//            displayArray(arr);
        }
    }

    /**
     * 中缀转后缀
     * (1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
     * (2) 从左至右扫描中缀表达式；
     * (3) 遇到操作数时，将其压入S2；
     * (4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
     * (4-1) 如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
     * (4-2) 否则，若优先级比栈顶运算符的高，也将运算符压入S1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；
     * (4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
     * (5) 遇到括号时：
     * (5-1) 如果是左括号“(”，则直接压入S1；
     * (5-2) 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；
     * (6) 重复步骤(2)至(5)，直到表达式的最右边；
     * (7) 将S1中剩余的运算符依次弹出并压入S2；
     * (8) 依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。
     */

    //定义运算符优先级
    static HashMap<String, Integer> pri = new HashMap<>();

    //初始化优先级
    public static void initPri() {
        pri.put("+", 1);
        pri.put("-", 1);
        pri.put("*", 2);
        pri.put("/", 2);
        pri.put("(", 2);
        pri.put(")", 2);
    }

    //1、初始化两个栈
    static Stack<String> s1 = new Stack<>(), s2 = new Stack<>();//s1运算符栈，s2结果栈

    //将中缀转后缀
    public static void suffix(String str) {
        if (str.equals("")) return;
        String[] arr = str.split("");
        //2、从左至右扫描中缀
        boolean preIsNumber = false;//用于记录上次push的是操作数还是运算符
        for (int i = 0; i < arr.length; i++) {
            if (pri.containsKey(arr[i])) {//4、是运算符，比较其与S1栈顶运算符的优先级：
                preIsNumber = false;
                boolean flag = true;
                if (arr[i].equals("(")) {//5-1、如果是左括号“(”，则直接压入S1
                    s1.push(arr[i]);
                    flag = false;
                } else if (arr[i].equals(")")) {//5-2、如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃
                    String oper = s1.pop();
                    while (!oper.equals("(")) {
                        s2.push(oper);
                        oper = s1.pop();
                    }
                    flag = false;
                }
                while (flag) {
                    if (s1.empty() || s1.peek().equals("(")) {//4-1、s1为空或s1栈顶为左括号'('
                        s1.push(arr[i]);
                        flag = false;
                    } else {//4-2、比较当前运算符和s1栈顶运算符的优先级
                        if (pri.get(s1.peek()) < pri.get(arr[i])) {//优先级高，压入s1
                            s1.push(arr[i]);
                            flag = false;
                        } else {//优先级低，则将S1栈顶的运算符弹出并压入S2，再次转到(4-1)与S1中新的栈顶运算符相比较
                            s2.push(s1.pop());
                        }
                    }
                }
            } else {//3、是操作数，压入s2
                if (preIsNumber) {
                    String pre = s2.pop();
                    pre += arr[i];
                    s2.push(pre);
                } else
                    s2.push(arr[i]);
                preIsNumber = true;
            }
        }
        while (!s1.empty()) {
            s2.push(s1.pop());
        }
    }

    /**
     * 后缀表达式求值
     * 1、从左向右扫描
     * 2、遇到数字压入栈中
     * 3、遇到运算符，弹出栈顶的2个数，并用运算符对这两个数进行运算，并将结果压入栈中
     * 4、重复步骤2~3，直至表达式最右侧，最后的值即为表达式结果
     */
    //计算后缀，此时s1为空，后缀表达式在s2中
    public static void calcSuffix() {
        Iterator<String> i = s2.iterator();
        while (i.hasNext()) {//1、从左向右扫描
            String c = i.next();
            if (pri.containsKey(c)) {//3、遇到运算符，弹出栈顶的2个数，并用运算符对这两个数进行运算，并将结果压入栈中
                double num2 = Double.parseDouble(s1.pop().toString());//注意，先取出的为第二个操作数，否则会导致结果出错
                double num1 = Double.parseDouble(s1.pop().toString());
                double result = 0;
                switch (c) {
                    case "+":
                        result = num1 + num2;
                        s1.push(result + "");
                        break;
                    case "-":
                        result = num1 - num2;
                        s1.push(result + "");
                        break;
                    case "*":
                        result = num1 * num2;
                        s1.push(result + "");
                        break;
                    case "/":
                        result = num1 / num2;
                        s1.push(result + "");
                        break;
                }
            } else {//2、遇到数字压入栈中
                s1.push(c);
            }
            System.out.println("s2.val=" + c);
        }
        System.out.println("s1.val=" + s1.toString());
    }

    /**
     * 中缀转后缀End===============================================================================================================
     */

    public static void Dp2Px() {
        int w = 1200, h = 1920, inch = 8;
        double dpi = Math.sqrt((w * w) + (h * h)) / inch;
        System.out.println("dpi = " + dpi);
        double px = 1 * dpi / 160;
        System.out.println("1dp = " + px + "px");
    }
}
